868F - Yet Another Minimization Problem - CodeForces Solution

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#define ll long long
#define reg register
#define fo(a,b,c) for(reg ll a=b;a<=c;a++)
#define re(a,b,c) for(reg ll a=b;a>=c;a--)
#define pii pair<ll,ll>
#define fi first
#define se second
#define mod 998244353
using namespace std;
inline ll gi(){
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
ll n,k;
ll a[100005],dp[100005][22],z,y,ans,t[100005];
ll ck(ll mz,ll my)
{
	while(y<my)
	{
		y++;
		ans+=t[a[y]];
		t[a[y]]++;
	}
	while(z<mz)
	{
		t[a[z]]--;
		ans-=t[a[z]];
		z++;
	}
	while(y>my)
	{
		t[a[y]]--;
		ans-=t[a[y]];
		y--;
	}
	while(z>mz)
	{
		z--;
		ans+=t[a[z]];
		t[a[z]]++;
	}
//	cout<<z<<" "<<y<<" "<<ans<<'\n';
	return ans;
}
void sol(ll num,ll l,ll r,ll pl,ll pr)
{
	ll mid=(l+r)/2;
	ll id=0,zs=999999999999999;
	fo(i,pl,min(mid,pr))
	{
//		cout<<i+1<<" "<<mid<<'\n';
		ll zzz=dp[i][num-1]+ck(i+1,mid);
		if(zzz<zs)
		{
			id=i;
			zs=zzz;
		}
	}
	dp[mid][num]=zs;
	if(l==r) return;
	sol(num,l,mid,pl,id);
	sol(num,mid+1,r,id,pr);
}
int main()
{
	t[0]=1;
	n=gi(),k=gi();
	fo(i,1,n)
	{
		dp[i][0]=999999999999999;
		a[i]=gi();
	}
	fo(i,1,k)
	{
		sol(i,1,n,0,n);
/*		fo(j,1,n)
		{
			cout<<dp[j][i]<<" ";
		}
		cout<<'\n';*/
	}
	cout<<dp[n][k];
	return 0;
}